/**
 * 切割钢材问题
 * 钢材价格，0～10英寸的价格 p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
 */

let p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

function rec_cutRod(n) {
    // 当长度为0时，没有收益，返回0
    if(n === 0) return 0;
    let rp = 0;
    for(let i = 1; i <= n; i++){
        // 对比当前的利润，和切成i,与n-i继续切割的和，取较大的那个
        rp = p[i]
        for(let j = 1; j < i; j++) {
            rp = rp > rec_cutRod(j) + rec_cutRod(i - j) ? rp : rec_cutRod(j) + rec_cutRod(i - j)
        }
    }
    return rp;
}

// console.log(4,'-------', rec_cutRod(4))
// console.log(10, '-------', rec_cutRod(10))

function cutRod(n) {
    if(n === 0) return 0;
    let dp = []
    for(let i = 1; i <=n; i++) {
        let res = p[i];
        for(let j = 1; j < i; j++) {
            res = res > p[j] + dp[i - j] ? res : p[j] + dp[i - j]
        }
        dp[i] = res;
    }
    return dp[n];
}
console.log(4,'-------', cutRod(4))
console.log(10, '-------', cutRod(10))